// run: $exec < input
#include <iostream>
#include <unordered_set>

int const maxn = 5500;
int const max_num = 32000;
int not_prime[max_num];
int bad_prime[maxn];
int good_prime[maxn];
int prefix_gcd[maxn];
int a[maxn], b[maxn];
int n, m, tot;

std::unordered_set<int> is_bad;

void init()
{
	for (int i = 2; i < max_num; i++)
		if (!not_prime[i]) {
			if (is_bad.find(i) == is_bad.end())
				good_prime[tot++] = i;
			for (int j = 2 * i; j < max_num; j += i)
				not_prime[j] = true;
		}
}

int gcd(int x, int y)
{
	return (!y) ? x : gcd(y, x % y);
}

int calc(int x, int t, int & common)
{
	int count = 0, tx = x;
	for (int i = 0; i < m; i++)
		for (; !(x % bad_prime[i]); x /= bad_prime[i]) count++;
	for (int i = 0; i < tot; i++)
		for (; !(x % good_prime[i]); x /= good_prime[i]) count--;
	if (x > 1) count--;
	if (count > 0) common *= tx;
	return std::max(0, count * t);
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> n >> m;
	for (int i = 0; i < n; i++) std::cin >> a[i];
	for (int i = 0; i < m; i++) {
		std::cin >> bad_prime[i];
		is_bad.insert(bad_prime[i]);
	}
	init();

	for (int i = 0; i < n; i++) b[i] = a[i];
	int ans = 0;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			int count = 0;
			for (; !(b[j] % bad_prime[i]); b[j] /= bad_prime[i])
				count++;
			ans -= count;
		}
	}

	for (int i = 0; i < n; i++) {
		int count = 0;
		for (int j = 0; j < tot; j++) {
			for (; !(b[i] % good_prime[j]); b[i] /= good_prime[j])
				count++;
		}
		if (b[i] > 1) count++;
		ans += count;
	}

	prefix_gcd[0] = a[0];
	for (int i = 1; i < n; i++)
		prefix_gcd[i] = gcd(prefix_gcd[i - 1], a[i]);
	int common = 1;
	for (int i = n - 1; i >= 0; i--) {
		prefix_gcd[i] /= common;
		ans += calc(prefix_gcd[i], i + 1, common);
	}
	std::cout << ans << '\n';
}

